ASP Advantage 1994 2nd Q2

home *** CD-ROM | disk | FTP | other *** search

/ ASP Advantage 1994 2nd Q2 / The Association of Shareware Professionals - The Official ASP Advantage (2nd Quarter)(1994).bin / files / progming / timstk11 / readme3.txt < prev next >

Wrap

Text File | 1993-04-01 | 17.4 KB | 466 lines

T i m e S t a c k The Ultimate Software Timing and Stack Analysis Utility Worst Case Timing And Stack Analysis Increases Quality and Confidence During the late 1600's Sir Isaac Newton revolutionized the scientific community with his laws of gravity and planetary motion. At the time, these laws appeared flawless. However, as new discoveries came to light, it became apparent that Newton's laws did not work when pushed to their extremes. By the early 20th century, Albert Einstein had developed a new set of laws that worked even at the speed of light. Many software programs suffer from the same malady. They work fine under normal conditions, but break down when pushed to the extreme. How Many Errors Many studies have been done to determine the number of defects in a software program. Figure 1 shows the results from the University of Maryland's Software Engineering Laboratory. They measured defects in software created at NASA's Goddard Space Center. While it is clear that quality is improving, it will never reach perfection. 1 TimeStack - The Software Timing and Stack Analysis Tool Bugs, Errors, Defects X - Worst 12 -| * - Average | X O - Best | 10 -| X | X | * X 8 -| * | * X | O * X 6 -| O O * * X | O O * X | O O *O 4 -| | | 2 -| | | 0 -+---+-----+-----+-----+-----+-----+-----+-----+- 76 78 80 82 84 86 88 90 Year Figure 1 Number of bugs, Errors, Defects per 1,000 Lines of Code Testing software is not easy. It is not unusual to find that a program thoroughly tested by conventional methods still contains fatal flaws. AT&T learned the lesson the hard way on January 15, 1990. A slight software error disabled nearly half their long distance lines around the country for almost nine hours. Error Sensitivity Obviously software is extremely sensitive to small errors. Mechanical parts can accommodate a small variance. Unfortunately, computers only understand right or wrong; they cannot interpret gray areas. One tiny error can snowball into a disaster. Sooner or later, every product is asked to perform at its limits. However uncommon the situation, when it happens, will your software meet the challenge? 2 TimeStack - The Software Timing and Stack Analysis Tool What Can Go Wrong For someone who writes complex software, it doesn't take much of an imagination to understand how many things can go wrong. And, depending upon the product the software controls, an error can cause a malfunction resulting in annoyance at the least or a disaster in critical situations. Execution time is one area where errors can slip by until it's too late. A program may get some combination of inputs that cause it to run longer than its typical time. Then what? A critical task could get skipped or run out of order. Tasks could begin to nest and/or exhaust their stack space. The initial small error has become a huge problem. Sometimes a programming or compiler error allows an imbalanced stack. Something could get put on the stack but not taken off. Once again, a huge problem can result from an initial small error. The Solution The answer to all of these questions is a TimeStack analysis. This analysis will provide, in detail, for every function, the theoretical: * maximum execution time, * minimum execution time, * worst stack depth usage, and * possible stack imbalances. Maximum Execution Time The theoretical maximum execution time is found by looking at all possible combination of paths that a function can take. This is difficult at best to do by hand for small programs, almost impossible for programs of any significant size. In programs that must execute in a given time, this information is essential. 3 TimeStack - The Software Timing and Stack Analysis Tool Minimum Execution Time The quickest path through a function is also found. This is important if some processing must always take place. A too short execution time could indicate that a critical function is being skipped. Worst Stack Depth It is important to know how much stack a function uses. A typical amount may not be the same as its worst case. An overflowed stack usually means overwriting something important. Almost always the problem crops up at a distant point from the initial overflow and that makes it difficult to find. Stack Imbalances Most assembly language programmers have accidentally done this. A typical error would involve putting something on the stack and forgetting to take it off, or taking the wrong amount off. A more subtle stack imbalance occurs when saving values in the midst of complex logic. With the use of conditional branches, the possibility arises of putting something on the stack, while a complex path bypasses its removal. Number of Paths Obviously, the more paths involved in a complex algorithm, the more possibility for error exists. A program with only one or two conditional branches is relatively easy to time and check. But, the possible number of paths rises exponentially with the addition of each conditional branch. The worst case or maximum number of paths in a program increases by 2^n where 'n' is the number of conditional branches. The minimum number of paths is n + 1. In the typical program, neither of these extremes are realistic. However, they do provide a set of boundaries. Figure 2 shows these limits graphed as a function of the number of conditional branches. 4 TimeStack - The Software Timing and Stack Analysis Tool Possible paths X - Worst 100000 -| X O - Best | | 10000 -| O | | 1000 -| X O | | 100 -| O | X | 10 -| O | | XO 1 -+---XO------+-------+-------+-------+-------+- 0 1 10 100 1000 10000 Number of conditional branches Figure 2 Number of Paths vs. Number of Conditional Branches Most programs average a conditional branch every 10 to 20 bytes. A small 100 byte function would thus have an average of least five conditional branches. That means just this simple procedure all by itself would have between six and 32 possible paths. Now imagine how many paths a 100K program must have! How To Check How do the engineers in your company time and check their programs? Have they ever been checked completely? Clearly, a program of any complexity quickly becomes almost impossible to check. Many times it becomes necessary to just cross your fingers and hope it works. The methods most commonly used simply cannot handle complex programs. Impractical To Do It Manually With the number of possible paths in a program of any complexity, it is apparent that hand counting the execution time is a near-impossible task. Even if one were to sit and methodically examine each possible path, the probability of missing one is tremendous. And 5 TimeStack - The Software Timing and Stack Analysis Tool of course, the time wasted on this endeavor could be much more efficiently used for other aspects of programming. Logic Analyzers It would seem that a logic analyzer could do the job. It would -- but only if the software executes in a simple linear fashion. As long as there are no decisions to be made that can change the direction of flow, it will work fine. It becomes more complex if the timing depends upon the state of an input switch. Then you have to look at the switch in both positions. What if the timing depends on an interaction with a number of inputs? Or a calculated value? Using a logic analyzer quickly becomes cumbersome and is still unlikely to catch the absolute maximum path. Simulators A simulator relies upon user input to configure the simulator to try a finite number of branches. It will time the maximum execution time -- if you tell it which path that is. A simulator does not try every possible combination of execution paths looking for maximum and minimum execution times, deepest stack depth or stack imbalances. Even if the simulator follows a test suite, tests inputs at their limits or does random combinations in between, that still does not guarantee it will find the answers to those nagging questions. Profilers A profiler is no better than a logic analyzer. Once again, it depends upon the user to determine the inputs and execution paths. You can never be sure the maximum path or stack has been found. The Cost Of Failure When a software program fails to carry out its appointed task, it is difficult to calculate the cost of failure. Deciding how to assess these costs is a 6 TimeStack - The Software Timing and Stack Analysis Tool decision each company must come to on its own. It has been mentioned because it is important when balancing the cost of testing with the cost of failure. Slightly Pessimistic A timing and stack analysis has one weakness: the results may be slightly pessimistic with some algorithms. This is typically caused by functions that are mutually exclusive but are timed together anyway. Nevertheless, it would be nice to have that safe feeling that your program will perform even under unrealistic circumstances. And isn't it better to err on the conservative side? Standards for Government Software Development Government document DOD-STD-2167A relates to the acquisition, development, or support of software systems. In paragraph 4.2.1 it says "The contractor shall use systematic and well documented software development methods to perform ... testing of the deliverable software." Paragraph 5.4.2.5: "The contractor's ... testing shall include stressing the software at the limits of its specified requirements." It would seem prudent to include a TimeStack analysis to know where those limits are. Aviation Industry Guidelines Manufactures of aviation products have devised a series of guidelines for their equipment. Document RTCA/DO- 178A, titled "Software Considerations in Airborne Systems and Equipment Certification", proposes guidelines for software in avionics and flight critical functions. For obvious reasons, design, verification, and testing are very important in this area. It mentions the importance of execution flow and timing, measuring CPU utilization, and software input transient load effects. A TimeStack analysis is of great benefit to these types of programs. 7 TimeStack - The Software Timing and Stack Analysis Tool Bibliography F. W. Blakely and M. E. Boles, "A Case Study of Code Inspections," Hewlett-Packard Journal, Vol 42 no. 4, October 1991, pp. 58-63. F. P. Brooks, Jr., "The Mythical Man-month," Addison- Wesley, 1975. T. H. Cormen, C. E. Leiserson and R. L. Rivest, "Introduction to Algorithms," McGraw-Hill, 1990. R. B. Grady and D. L. Caswell, "Software Metrics: Establishing a Company-wide Program," Prentice-Hall, 1987. L. Lee, "The Day The Phones Stopped," Donald I. Fine, Inc., 1991. D. L. Parnas, A. J. van Schouwen, and S. P. Kwan, "Evaluation of Safety-Critical Software," Commun. ACM, Vol 33 no. 6, June 1990, pp. 636-648. R. Resnick and D. Halliday, "Physics, Part I," John Wiley & Sons, Third edition, 1977. E. I. Schwartz, "Turning Software From a Black Art into a Science," Business Week, October 25, 1991, pp. 80. W. T. Ward, "Calculating the Real Cost of Software Defects," Hewlett-Packard Journal, Vol. 42 no. 4, October 1991, pp. 55-58. 8